package com.midea.exam;

/**
 * @description：二分查找的两种实现
 * @author: wangwl23
 * @create: 2021-08-18 15:06
 */
public class BinarySearch {
    public static void main(String[] args) {

    }

    /**
     * while循环实现二分查找
     *
     * @param arr
     * @param key
     * @return
     */
    public static int whileBinarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int middle = 0;
        if (key < arr[low] || key > arr[high] || low > high) {
            return -1;
        }
        while (low <= high) {
            middle = (low + high) / 2;
            if (arr[middle] > key) {
                high = middle - 1;
            } else if (arr[middle] < key) {
                low = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

    /**
     * 递归实现二分查找
     *
     * @param arr
     * @param key
     * @return
     */
    public static int recursionBinarySearch(int[] arr, int key, int low, int high) {
        if (key < arr[low] || key > arr[high] || low > high) {
            return -1;
        }
        int middle = (low + high) / 2;
        if (arr[middle] > key) {
            return recursionBinarySearch(arr, key, low, middle - 1);
        } else if (arr[middle] < key) {
            return recursionBinarySearch(arr, key, middle + 1, high);
        } else {
            return middle;
        }
    }
}
